package org.example.day01;

import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0 +
 * @description: TODO
 * 小扇和小船今天又玩起来了数字游戏，小船给小扇一个正整数n (1<=n<=1e9)，
 * 小扇需要找到一个比n大的数字m，使得m和n对应的二进制中1的个数要相同
 * （如4对应二进制100,8对应二进制1000,1的个数都为1），现在求m的最小值
 * @date 2024/3/11 15:22
 */
public class test016 {
    public static int nextNumberWithSameBits(int n) {
        // 将输入的数字 n 转换为二进制表示，并找到第一个 "01" 模式的位置
        String binary_n = Integer.toBinaryString(n);
        String pattern = "01";
        int pos = binary_n.lastIndexOf(pattern);

        if (pos != -1) {
            // 找到 "01" 模式，替换为 "10"
            String binary_m = binary_n.substring(0, pos) + "10" + binary_n.substring(pos + 2);

            // 计算模式之后1的个数
            int ones_to_move = binary_m.substring(pos + 2).replaceAll("0", "").length();

            // 将这些1移到最低位
            StringBuilder sb = new StringBuilder();
            sb.append(binary_m.substring(0, pos + 2));
            for (int i = 0; i < binary_m.length() - pos - 2 - ones_to_move; i++) {
                sb.append("0");
            }
            for (int i = 0; i < ones_to_move; i++) {
                sb.append("1");
            }
            return Integer.parseInt(sb.toString(), 2);
        } else {
            // 如果没有找到 "01" 模式，说明 n 是类似 "1111" 的形式
            // 我们需要在最左侧添加 "10"，并将所有1移动到最右侧
            int ones_count = binary_n.replaceAll("0", "").length();
            StringBuilder sb = new StringBuilder();
            sb.append("10");
            for (int i = 0; i < binary_n.length() - ones_count; i++) {
                sb.append("0");
            }
            for (int i = 0; i < ones_count - 1; i++) {
                sb.append("1");
            }
            return Integer.parseInt(sb.toString(), 2);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = nextNumberWithSameBits(n);
        System.out.println(m);
    }
}
